package cn.bellychang.leetcode.question039;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ChangLiang
 * @date 2021/3/20
 */
public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> result = new ArrayList<>();
        combinationSum(candidates, target, result, new ArrayList<>(), 0);
        return result;
    }

    /**
     *
     * @param candidates
     * @param target
     * @param result
     * @param solution
     * @param start 从第一个元素开始尝试 而且初始子集为空
     */
    private void combinationSum(int[] candidates, int target, List<List<Integer>> result, List<Integer> solution, int start){

        if (target < 0) {
            return;
        }

        if (target == 0) {
            result.add(solution);
        }

        for (int i = start; i < candidates.length; i++) {
            solution.add(candidates[i]);
            // note: 这里要使用new ArrayList<>(solution)
            combinationSum(candidates, target - candidates[i], result, new ArrayList<>(solution), i);
            solution.remove(solution.size()-1);
        }

    }

}
